package linkedlist;

public class Josepfu {
    public static void main(String[] args) {

        //测试
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(100000); //创建节点
        circleSingleLinkedList.List();
        System.out.println("-------");
        circleSingleLinkedList.countBoy(60,70,100000);
    }
}


//创建一个环形单向链表
//first不能动！！！！！
class CircleSingleLinkedList{
    //创建一个first节点，当前没有编号
    private Boy first = null;

    //添加小孩节点，构建一个环形链表
    public void addBoy(int nums){
        //nums代表一共有几个节点
        if(nums < 1){
            System.out.println("nums必须大于1");
            return;
        }
        Boy curBoy = null;  //辅助指针，帮助构建环形链表
        //使用一个for循环来创建一个环形链表
        for(int i=1; i<=nums; i++){
            //根据编号，创建小孩节点
            Boy boy = new Boy(i);
            //如果是第一个小孩,需要构成环状
            if(i ==1){
                first=boy;
                first.setNext(first); //构成一个环
                curBoy = first;  //让curBoy指向第一个小孩
            }else{
                curBoy.setNext(boy); //将curBoy指向新创建的boy节点
                boy.setNext(first);  //然后将当前boy节点指向第一个节点
                curBoy = boy;  //然后把curBoy指向新节点boy,就是往后移一位而已。
            }
        }

    }

    //遍历当前环形链表
    public void List(){
        //判断链表是否为空
        if(first == null){
            System.out.println("链表为空");
            return;
        }
        //first不能动，因此需要一个辅助指针
        Boy curBoy = first;
        while (true){
            System.out.println("小孩的编号为："+curBoy.getNo());
            if(curBoy.getNext()==first){ //说明遍历完毕
                break;
            }
            curBoy = curBoy.getNext();  //curBoy后移
        }

    }

    //根据用户输入，计算出出圈的顺序
    /**
     *（约瑟夫问题）
     * @param startNo  表示从第几个小孩开始数数
     * @param countNum 表示数几下
     * @param nums 表示最初有多少个小孩
     */
    public void countBoy(int startNo, int countNum,int nums){
        //对数据校验
        if(first==null || startNo<1 || startNo>nums){
            System.out.println("参数输入有误");
        }
        //创建一个辅助指针，帮助完成小孩出圈
        Boy helper = first;
        //先让helper指向最后一个节点
        while (true){
            if(helper.getNext() == first){
                break;
            }
            helper = helper.getNext();
        }
        //小孩报数前，先让first和helper移动k-1次（也就是移动到指定位置）
        for(int j = 0 ; j<startNo-1; j++){
            first = first.getNext();
            helper = helper.getNext();
        }
        //开始出圈
        while (true){
            if(helper == first){
                //说明当前圈中只有一个节点
                break;
            }
            //让first和helper同时移动countNum-1次
            for(int j=0 ; j<countNum-1 ; j++){
                first = first.getNext();
                helper = helper.getNext();
            }
            //这个时候first指向的节点就是要出圈的
            System.out.println("当前出圈的小孩为："+first.getNo());
            //这个时候将first指向的小孩出圈
            first = first.getNext();  //先让first指向下一个节点
            helper.setNext(first);  //让helper指向first
        }
        //最后一个小孩
        System.out.println("最后一个小孩："+first.getNo());
    }
}

//创建一个Boy类，表示一个节点
class Boy{
    private int no;  //编号
    private Boy next; //指向下一个节点

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}